package uestc.lj.basic.recall;

/**
 * 背包问题
 *
 * @Author:Crazlee
 * @Date:2021/11/25
 */
public class Code08_Package {
	public static int maxValue1(int[] weights, int[] values, int bag) {
		return process1(weights, values, 0, 0, bag);
	}

	/**
	 * 背包问题
	 *
	 * @param weights       重量数组
	 * @param values        价值数组
	 * @param i             第i个物品
	 * @param alreadyweight 之前的所有重量
	 * @param bag           容量
	 * @return 最大价值
	 */
	public static int process1(int[] weights, int[] values, int i, int alreadyweight, int bag) {
		if (alreadyweight > bag) {

			return 0;
		}
		if (i == weights.length) {
			return 0;
		}

		return Math.max(process1(weights, values, i + 1, alreadyweight, bag),
				values[i] + process1(weights, values, i + 1, alreadyweight + weights[i], bag));
	}


	//==========================================================================================
	public static int maxValue2(int[] c, int[] p, int bag) {
		int[][] dp = new int[c.length + 1][bag + 1];
		for (int i = c.length - 1; i >= 0; i--) {
			for (int j = bag; j >= 0; j--) {
				dp[i][j] = dp[i + 1][j];
				if (j + c[i] <= bag) {
					dp[i][j] = Math.max(dp[i][j], p[i] + dp[i + 1][j + c[i]]);
				}
			}
		}
		return dp[0][0];
	}

	public static void main(String[] args) {
		int[] weights = {2, 3, 5, 5};
		int[] values = {2, 4, 3,7};
		int bag = 10;
		System.out.println(maxValue1(weights, values, bag));
		System.out.println(maxValue2(weights, values, bag));
	}

}
